import java.util.HashMap;
import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86132
 * Date: 2022-04-12
 * Time: 18:03
 */
public class Test {
    //710. 黑名单中的随机数
class Solution {
    int size=0;//白名单元素的个数
    HashMap<Integer,Integer> map=new HashMap<>();//用来记录黑名单的数据
    Random random=new Random();
    public Solution(int n, int[] blacklist) {
        size=n-blacklist.length;
        for(int b:blacklist){
            map.put(b,-1);//先将黑名单中的数随便放一个位置
        }
        int last=n-1;//[0,n)个元素中最后一个元素,同时也是最后一个元素所在是位置
        //将黑名单中的元素都移到后面去
        for(int b:blacklist){
            if(b>=size){//前size是白名单的元素，后面n-size是黑名单的元素
                continue;//如果黑名单的元素恰好已经在后面黑名单元素应在的位置就不用在移了，直接跳过当前循环
            }
            while(map.containsKey(last)){//当[0,n)个元素中最后一个元素是黑名单中的元素时，就跳过
                last--;
            }
            //此时last的值是一个白名单的值
            map.put(b,last);//给黑名单的元素b找到一个对应白名单的值last
            last--;
        }
    }

    public int pick() {
        int index=random.nextInt(size);//此时[0,size)的数都是白名单的数，直接通过random生成[0,size)的数即可
        if(map.containsKey(index)){//如果生成的是黑名单的数
            return map.get(index);//返回对应黑名单的数
        }
        return index;//如果生成的是白名单的数，直接返回即可
    }
}
}
